#include<bits/stdc++.h>
#define gc getchar
#define itn int
#define x first
#define y second
#define eb emplace_back
#define em emplace
#define pb push_back
#define db double
#define y1 yy1_yyds
using namespace std; typedef long long ll; typedef unsigned long long ull;
// https://www.luogu.com.cn/discuss/522581 About "const"
ll read() {
	ll x = 0; short fh = 1; char ch = gc();
	while (!isdigit(ch)) {
		if (ch == '-') fh = -1;
		if (ch < 10) exit(0); 
		ch = gc();
	}
	while (isdigit(ch))
		x = x * 10 + (ch ^ 48), ch = gc();
	return fh * x;
}
#ifndef ONLINE_JUDGE
void debug() {cerr << "\n";}
template<typename Typ1> void debug(Typ1 arg) {cerr << arg << "\n";}
template<typename Typ1, typename ...Typ2> void debug(Typ1 arg, Typ2 ...args) {
	cerr << arg << " ", debug(args...);
}
#else
void debug() {}
template<typename Typ1> void debug(Typ1 arg) {}
template<typename Typ1, typename ...Typ2> void debug(Typ1 arg, Typ2 ...args) {}
#endif
void writeln(ll arg) {printf("%lld\n", arg);}
template<typename ...Typ2> void writeln(ll arg, Typ2 ...args) {
	printf("%lld ", arg), writeln(args...);
}
typedef pair <int, int> pii; typedef pair <ll, ll> pll;
const char Y_E_S[] = "YES", N__O[] = "NO";
// const char Y_E_S[] = "Yes", N__O[] = "No";
// #define infinite_testcase
#define multiple_testcase
// #define output_Yes_No
const int DUST = 327, N = 2145, M = -1;
int mod;
// ll fact[N * N], inv[N * N];
ll qp(ll a, ll b) {
    ll ans = 1;
    for(; b; b >>= 1, a = a * a % mod) if(b & 1) ans = ans * a % mod;
    return ans;
}
// void C_init() {
    // const int n = 4e6 + 3;
    // *fact = 1;
    // for(int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % mod;
    // inv[n] = qp(fact[n], mod - 2);
    // for(int i = n - 1; ~i; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
// }
// ll C(ll n, ll m) {
    // if(m > n) return 0;
    // if(m < 0) return 0;
    // return fact[n] * inv[m] % mod * inv[n - m] % mod;
// }
int dp[214][214 * 214];
void add(int &a, int b) {a += b; if(a >= mod) a -= mod;}
void sub(int &a, int b) {a -= b; if(a < 0) a += mod;}
bool major(int Case = 1) {
	debug(sizeof dp / 1048576.);
	int n = read(), m = read();
	dp[0][0] = 1;
	for(int i = 1; i <= n; i++) {
		// int sum = 0, sum2 = 0;
		int r = 0;
		for(int j = 0; j <= i * m; j++) {
			add(r, dp[i - 1][j]);
			if(j > m) sub(r, dp[i - 1][j - m - 1]);
		// /**/dp[i][j] = 0;
			dp[i][j] = r;
			// for(int k = 0; k <= min(j, m); k++)
				// add(dp[i][j], dp[i - 1][j - k]);
			// debug(i, j, dp[i][j]);
			// add(sum, dp[i][j]), add(sum2, dp[i][j] * 1ll * dp[i][j] % mod);
		}
		// printf("[");
		// for(int j = 0; j <= i * m; j++) printf("%d%c", dp[i][j], " ]"[j == i * m]);
		// printf("\ni = %d, sum1 = %d, sum2 = %d\n\n", i, sum, sum2);
	}
	int sum2 = 0;
	for(int j = /*1*/0; j <= n * m; j++)
		add(sum2, dp[n][j] * 1ll * dp[n][j] % mod);
	// debug(sum2);
	ll full = qp(m + 1, n << 1);
	ll ans = (full - sum2 + mod) % mod;
	ans = ans * qp(2, mod - 2) % mod;
	ans = ans * qp(full, mod - 2) % mod;
	writeln(ans);
	return Case ^= Case ^ Case;
}
void initial_function(int argc, char **argv) {
	**argv = argc; /* <- place_holder
	you won't give up no matter what happens, will you?
	code time: >> 10:04
	---
	
	*/
	freopen("pr.in", "r", stdin);
	freopen("pr.out", "w", stdout);
	mod = read();
	// C_init();
}
signed main(int argc, char **argv) {
	initial_function(argc, argv);
	int Case = 1, Maxcase = 1;
	for (
#ifdef multiple_testcase
		  Maxcase = read()
#endif
				     	  ;
#ifndef infinite_testcase
							Case <= Maxcase
#endif
				     					   ; Case++)
#ifdef output_Yes_No
		puts(major(Case) ? Y_E_S : N__O);
#else
		major(Case);
#endif
	return DUST ^ 0x147;
}
